package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-25 17:33
 **/
public class LeetCode102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        //用于存储层序遍历的数据
        List<List<Integer>> list = new ArrayList<>();
        //节点为空直接返回
        if (root == null) {
            return list;
        }
        //使用队列的数据结构存储遍历的节点
        Deque<TreeNode> deque = new LinkedList<>();
        //根节点入队
        deque.offer(root);
        //用来存储每一层的所有队列
        List<Integer> listTemp = null;
        //按层遍历节点
        while (!deque.isEmpty()) {
            //存储当前层的元素个数
            int size = deque.size();
            listTemp = new ArrayList<>();
            while (size > 0) {
                //从左往右获取当层节点
                TreeNode node = deque.poll();
                //把当层节点的值放到列表中
                listTemp.add(node.val);
                //若当前节点的左节点不为空，当前节点的左节点入队
                if (node.left != null) {
                    deque.offer(node.left);
                }
                //若当前节点的右节点不为空，当前节点的右节点入队
                if (node.right != null) {
                    deque.offer(node.right);
                }
                //缩小当前层的元素个数
                size--;
            }
            //把当前层的list放到总的list中。
            list.add(listTemp);
        }
        return list;
    }

}
